#include<stdio.h>
#include<stdlib.h>
struct node//链表结构体 
{
    int data;//数据域 
    struct node* next;//指向下一个结构体的指针 
};
node* create(int data)//新建链表项（新结构体） 
{
    node* newNode = (node*)malloc(sizeof(node));//给这个结构体开空间 
    newNode->data = data;//保存数据 
    newNode->next = NULL;//指针为空 
    return newNode;//返回新建的结构体 
}

int main()
{
    struct node *p,*q,*t,*h;//定义几个临时变量，会用到 
    int tmp;
    
    //输入集合A 
    scanf("%d", &tmp);
    struct node* head_a = create(tmp);//头节点 
    p = head_a;//p是临时变量 
    while (scanf("%d", &tmp) && tmp != -1)//输入数字，且当tmp=-1的时候结束 
    {
        struct node* a = create(tmp);//给链表A新建节点 
        p->next = a;//上一个节点的指针指向现在这个 
        p = a;//临时变量变成现在这个 
    }
    
    //输入集合A 
    scanf("%d", &tmp);
    struct node* head_b = create(tmp);//头节点 
    p = head_b;//p是临时变量 
    while (scanf("%d", &tmp) && tmp != -1)//输入数字，且当tmp=-1的时候结束
    {
        struct node* b = create(tmp);//给链表A新建节点
        p->next = b;//上一个节点的指针指向现在这个
        p = b;//临时变量变成现在这个 
    }
    
    struct node* head_jiao = create(-1);//定义交集的头结点 
    struct node* head_bing = create(-1);//定义并集的头结点 
    struct node* head_cha = create(-1);//定义差集的头结点 
    
    /*
    交集思路：
    遍历A，对A的每个元素 ，都与B中的元素进行一一对比
    类似于for循环中的
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            比较a和b
        }
    }
    */ 
     
    p=head_a;//p是临时变量，从A的头开始 
    t=head_jiao;//t是临时变量，用来存交集的链表 
    while(p!=NULL)//链表A非空 ，遍历A链表 
    {
        
        q=head_b;//q是临时变量 ，从B的头开始 
        while(q!=NULL)//链表B非空 ，遍历B链表 
        {
            if(q->data==p->data)//B元素=A元素 
            {
                //如果a和b中有相同元素，则存进交集链表中 
                //以下操作与输入A,B集合同原理 
                struct node* jiao = create(p->data);//尾插法
                t->next = jiao;
                t = jiao;
                break;//因为找到了，所以break掉，去比较A的下一个元素 
            }
            q=q->next;//链表B的当前位置后移（q->next是下一个元素，让q=下一个元素 
        }
        p=p->next;//链表A的当前位置后移（p->next是下一个元素，让p=下一个元素 
    }
    /*
    输出交集
    因为head_jiao->data头节点的数据域中存的是-1（见上文定义交集头结点 
    故从head_jiao的下一个开始
    */
    t=head_jiao->next;
    while(t!=NULL)//遍历交集链表 
    {
        printf("%d->",t->data);//输出元素，记得加空格 
        t=t->next;//后移 
    }
    //Attention:这个-1不应该被放在链表中 
    printf("\n");//最后的元素以-1结尾，记得加换行 
    
    /*
    并集思路：
    先复制A的所有元素在并集bing里面
    然后遍历B，将B的每一个元素都与bing中元素比较
    若比较到最后都不一样，则当前元素不在bing中
    将这个元素添加进bing的末尾 
    */
    }
    p=head_a;//p是临时变量，从A的头开始
    t=head_bing;//t是临时变量，用来存并集的链表
    while(p!=NULL)//遍历链表A 
    {
        //以下操作与输入A,B集合同理，使用链表A的数据 
        struct node* bing = create(p->data);
        t->next = bing;
        t = bing;
        p=p->next;//链表A的当前位置后移（p->next是下一个元素，让p=下一个元素 
    }
    q=head_b;//q是临时变量，从B的头开始 

    while(q!=NULL)//遍历链表B
    {
        h=head_bing;//h是临时变量，读取并集的链表
        int flag=0;//用flag来记录是否有相同元素 
        while(h!=NULL)//遍历并集
        {
            if(h->data==q->data)//存在相同元素
            { 
                flag=1;
                break;
            }
            h=h->next;//后移
        }
        if(!flag)//如果不存在相同元素
        {
            //以下操作与输入A,B集合同理，使用链表B的当前元素数据 
            //t还是上面复制的时候定义的那个，继续相同操作 
            struct node* bing = create(q->data);
            t->next = bing;
            t = bing;
        }
        q=q->next;//后移 
    }
    /*
    输出并集
    因为head_bing->data头节点的数据域中存的是-1（见上文定义并集头结点 
    故从head_bing的下一个开始
    */ 
    t=head_bing->next;
    while(t!=NULL)//遍历并集链表 
    {
        printf("%d->",t->data);//输出元素，记得加空格 
        t=t->next;//后移 
    }
    //Attention:这个-1不应该被放在链表中 
    printf("\n");//最后的元素以-1结尾，记得加换行
    
    /*
    差集思路：
    同并集，先复制链表A在链表cha里面
    再遍历链表B，如果遇到元素在链表A中，则删除链表节点
    */
    p=head_a;//p是临时变量，从A的头开始
    t=head_cha;//t是临时变量，用来存差集的链表
    while(p!=NULL)//遍历链表A 
    {
        //以下操作与输入A,B集合同理，使用链表A的数据 
        struct node* cha = create(p->data);
        t->next = cha;
        t = cha;
        p=p->next;//链表A的当前位置后移（p->next是下一个元素，让p=下一个元素 
    }

    q=head_b;//q是临时变量，从head_b的头开始
    while(q!=NULL)//遍历链表
    {
        h=head_cha;//h是临时变量，从cha的第1个开始 
        t=head_cha->next;//t是临时变量，从cha的第2个开始 
        while(t!=NULL)//遍历cha差集，寻找当前数，然后把它删了 
        {
            if(t->data==q->data)//如果相等，删除 
            {
                h->next=t->next;//跳过t指向下一个 
                break;
            }
            //如果没删除，后移 
            h=h->next;
            t=t->next;
        }
        q=q->next;//后移 
    }
    
    /*
    输出差集
    因为head_cha->data头节点的数据域中存的是-1（见上文定义并集头结点 
    故从head_cha的下一个开始
    */ 
    t=head_cha->next;
    while(t!=NULL)//遍历差集链表 
    {
        printf("%d->",t->data);//输出元素，记得加空格 
        t=t->next;//后移 
    }
    //Attention:这个-1不应该被放在链表中 
    printf("\n");//最后的元素以-1结尾，记得加换行
    
    return 0;
}
